Valid palindrome II

Time: O(N); Space: O(1); easy

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: s = “aba”

Output: True

Example 2:

Input: s = “abca”

Output: True

Explanation:

  • You could delete the character ‘c’.

Constraints:

  • The string will only contain lowercase characters a-z.

  • The maximum length of the string is 50000.

[1]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        def validPalindrome(s, left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left, right = left+1, right-1
            return True

        left, right = 0, len(s)-1
        while left < right:
            if s[left] != s[right]:
                return validPalindrome(s, left, right-1) or validPalindrome(s, left+1, right)
            left, right = left+1, right-1
        return True

[2]:

sol = Solution1()

s = "aba"
assert sol.validPalindrome(s) == True

s = "abca"
assert sol.validPalindrome(s) == True